/*
 * 版权所有(C)，方太互联网应用技术部，lizhixing，所有权利保留。
 * <p>
 * 项目名：	algorithm-demo
 * 文件名：	Question128
 * 模块说明：
 * 修改历史：
 * 2025/2/7 - lizhixing - 创建。
 */
package com.lovely602.algorithm.wansuanfa;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 * <p>
 * 示例1： 输入：nums = [100,4,200,1,3,2]
 * <p>
 * 输出：4
 * <p>
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * <p>
 * 示例2： 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * <p>
 * 输出：9
 */
public class Question128 {


  public static void main(String[] args) {

    int[] nums = { 100, 4, 200, 1, 3, 2 };
    Question128 question = new Question128();
    System.out.println(question.longestConsecutive(nums));

  }

  public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums)
      set.add(num);// 元素存储到集合set中
    int maxLen = 0;
    for (int num : nums) {
      if (!set.contains(num - 1)) {// 判断是否是起始位置
        int curNum = num;
        // 从起始位置开始查找连续序列的长度
        int len = 1;
        while (set.contains(curNum + 1)) {
          curNum++;
          len++;
        }
        maxLen = Math.max(maxLen, len);
      }
    }
    return maxLen;
  }

}
